B. Substring and Subsequence

给你两个字符串 ab ,都由小写字母组成。字符串的子串是从原始字符串中删除几个(可能是零)字符后得到的字符串。

你的任务是计算使得 a 作为子串和 b 作为子序列的字符串的最小可能长度。

我的方法是三层循环的,如果数据严格一点肯定过不了的。

void solve() {
    string a, b;cin >> a >> b;
    int ans = 0;
    for (int i = 0;i < a.size();i++) {
        for (int j = 0;j < b.size();j++) {
            if (a[i] == b[j]) {
                int p = i;int x = 0;
                for (int k = j;k < b.size() && p < a.size();p++) {
                    if (a[p] == b[k]) {
                        x++;k++;
                    }
                }
                ans = max(ans, x);
            }
        }
    }
    cout << a.size() + b.size() - ans << '\n';
}

官方题解:两层循环:

void solve() {
    string a, b;cin >> a >> b;
    size_t ans = a.size() + b.size();
    for (int i = 0; i < b.size(); ++i) {
        int j = i;
        for (auto c : a) {
            if (j < b.size() && c == b[j]) ++j;
        }
        ans = min(ans, a.size() + b.size() - (j - i));
    }
    cout << ans << '\n';
}